#define  _CRT_SECURE_NO_WARNINGS 1
typedef struct Node Node;
Node* copyRandomList(Node* head) {
    if (head == NULL) {
        return NULL;
    }

    Node* cur = head;
    while (cur) {
        Node* copy = (Node*)malloc(sizeof(Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }

    cur = head;
    while (cur) {
        Node* copy = cur->next;
        if (cur->random == NULL) {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }

    cur = head;
    Node* newhead = NULL;
    Node* newTail = NULL;
    Node* copy = NULL;

    while (cur) {
        copy = cur->next;
        cur->next = copy->next;
        if (newTail == NULL)
        {
            newhead = newTail = copy;
        }
        else {
            newTail->next = copy;
            newTail = newTail->next;
        }
        cur = cur->next;
    }

    return newhead;
}
